package 力扣;

/**
 * @author yyq
 * @create 2022-03-01 10:22
 * 剑指 Offer II 095. 最长公共子序列
 * 解题思路:采取动态规划，利用空间换时间
 *
 */
public class offerII095LongSequence {
    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace"));
        System.out.println(longestCommonSubsequence("abc", "abc"));
        System.out.println(longestCommonSubsequence("abc", "def"));

    }
    public static int longestCommonSubsequence(String text1, String text2) {
        //  创建缓存数组，maxlength[1][2]代表text1[0-1]和text2[0-2]中的最长公共子序列长度
        int[][] maxlenth=new int[text1.length()+1][text2.length()+1];
        // 第一行和第一列为空
        for (int i=0;i<maxlenth[0].length;i++)
            maxlenth[0][i]=0;
        for (int i=0;i<maxlenth.length;i++)
            maxlenth[i][0]=0;
        //  循环遍历缓存数组，生成数组的每一个数值
        for (int i = 1; i < maxlenth.length; i++) {
            for (int j = 1; j < maxlenth[0].length; j++) {
                int a=i-1;
                int b=j-1;
                // 情况一 如果当前的位置对应的字符相同
                if(text1.charAt(a)==text2.charAt(b)){
                    maxlenth[i][j]=maxlenth[i-1][j-1]+1;
                }
                // 情况二 对应的字符不相同
                else {
                    int max=maxlenth[i-1][j];
                    if(maxlenth[i][j-1]>max){
                        max=maxlenth[i][j-1];
                    }
                    maxlenth[i][j]=max;
                }
            }
        }
        return maxlenth[text1.length()][text2.length()];
    }
}
